package vn.edu.hut.soict.automaton;

import java.util.ArrayList;
import java.util.List;

public class DFA<T> {
	public static final int START_STATE_ID = 0;

	private int maxStateID;

	private List<State<T>> states;

	public DFA() {
		maxStateID = 0;
		states = new ArrayList<State<T>>();
		states.add(new State<T>(this, START_STATE_ID));
	}

	public List<State<T>> getStates() {
		return states;
	}

	public State<T> getStartState() {
		return states.get(START_STATE_ID);
	}

	public State<T> getStateByID(int stateID) {
		return states.get(stateID);
	}

	public State<T> addNewState() {
		maxStateID++;
		State<T> state = new State<T>(this, maxStateID);
		states.add(state);
		return state;
	}

	public void deleteState(State<T> state) {
		if (state != null) {
			List<Transition<T>> nextTransitions = state.getNextTransitions();
			List<Transition<T>> prevTransitions = state.getPrevTransitions();
			for (Transition<T> transition : nextTransitions) {
				State<T> target = transition.getTarget();
				target.getPrevTransitions().remove(transition);
			}
			for (Transition<T> transition : prevTransitions) {
				State<T> source = transition.getSource();
				source.getNextTransitions().remove(transition);
			}
			states.set(states.indexOf(state), null);
		}
	}

	public boolean addTransition(Transition<T> transition) {
		State<T> source = transition.getSource();
		State<T> target = transition.getTarget();
		if (source == null || target == null) {
			return false;
		}
		source.getNextTransitions().add(transition);
		target.getPrevTransitions().add(transition);
		return true;
	}

	Transition<T> findFirstTransition(State<T> source, T symbol) {
		if (source != null) {
			for (int i = 0; i < source.getNextTransitions().size(); i++) {
				if (source.getNextTransitions().get(i).getSymbol().equals(symbol)) {
					return source.getNextTransitions().get(i);
				}
			}
		}
		return null;
	}

	public boolean accept(T[] string) {
		State<T> state = getStartState();
		for (int i = 0; i < string.length && state != null; i++) {
			Transition<T> curr = findFirstTransition(state, string[i]);
			if (curr == null) {
				state = null;
			}
			else {
				state = curr.getTarget();
			}
		}
		return state != null && state.isFinal();
	}

	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < states.size(); i++) {
			if (states.get(i) != null) {
				List<Transition<T>> nextTransitions = states.get(i).getNextTransitions();
				for (int j = 0; j < nextTransitions.size(); j++) {
					sb.append(nextTransitions.get(j).toString()).append("\n");
				}
			}
		}
		return sb.toString();
	}
}
